A sparse matrix representation typically represents and/or stores only non-zero elements of the matrix, in contrast to a dense representation which stores all elements regardless of their value. Matrix sparsity refers to the number and pattern of non-zeros in a particular matrix. In the context of a graphics processing environment, sparse matrices are often derived from an unstructured mesh, etc. To date, many systems are equipped for performing operations (e.g. matrix-vector multiplication, etc.) efficiently on dense matrices. Parallel processing architectures (e.g. graphics processors, etc.) are examples of such systems.
Thus, in situations where a sparse matrix is operated upon with such systems, performance tends to be less than desirable. For example, such systems may exhibit incoherent memory accesses, potential work imbalance amongst processing threads, etc.